package com.mid;

/**
 * Created by Lxk on 2019/5/13.
 */
public class Solution62 {

    private int findAllPath(int x,int y){
        if(x==1 || y==1){
            return 1;
        }
        return findAllPath(x-1,y) + findAllPath(x,y-1);
    }

    public int uniquePaths(int m, int n) {
        return findAllPath(n,m);
    }

    public static int uniquePathsDp(int m, int n) {
        int[] dp = new int[m];
        for(int x = 0;x < m; x++){
            dp[x] = 1;
        }
        for(int x = 1; x < n; x++){
            for(int y = 1; y < m; y++){
                dp[y] = dp[y-1] + dp[y];
            }
        }
        return dp[m-1];
    }



    public static void main(String[] args) {
        System.out.println(uniquePathsDp(3,2));
    }

}
